最后一遍-L30-Substring with Concatenation of All Words
//You are given a string s and an array of strings words of the same length. Ret
//urn all starting indices of substring(s) in s that is a concatenation of each wo
//rd in words exactly once, in any order, and without any intervening characters.
//
//
// You can return the answer in any order.
//
//
// Example 1:
//
//
//Input: s = "barfoothefoobarman", words = ["foo","bar"]
//Output: [0,9]
//Explanation: Substrings starting at index 0 and 9 are "barfoo" and "foobar" re
//spectively.
//The output order does not matter, returning [9,0] is fine too.
//
//
// Example 2:
//
//
//Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
//Output: []
//
//
// Example 3:
//
//
//Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
//Output: [6,9,12]
//
//
//
// Constraints:
//
//
// 1 <= s.length <= 104
// s consists of lower-case English letters.
// 1 <= words.length <= 5000
// 1 <= words[i].length <= 30
// words[i] consists of lower-case English letters.
//
// Related Topics Hash Table String Sliding Window
// 👍 2050 👎 1896
按照题目的意思，进行编码
首先是使用HashMap的算法
class Solution {
private HashMap<String, Integer> wordCount = new HashMap<String, Integer>();
private int wordLength;
private int substringSize;
private int k;
private boolean check(int i, String s) {
// Copy the original dictionary to use for this index
HashMap<String, Integer> remaining = new HashMap<>(wordCount);
int wordsUsed = 0;
// Each iteration will check for a match in words
for (int j = i; j < i + substringSize; j += wordLength) {
String sub = s.substring(j, j + wordLength);
if (remaining.getOrDefault(sub, 0) != 0) {
remaining.put(sub, remaining.get(sub) - 1);
wordsUsed++;
} else {
break;
}
}
return wordsUsed == k;
}
public List<Integer> findSubstring(String s, String[] words) {
int n = s.length();
k = words.length;
wordLength = words[0].length();
substringSize = wordLength * k;
for (String word : words) {
wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
}
List<Integer> answer = new ArrayList<>();
for (int i = 0; i < n - substringSize + 1; i++) {
if (check(i, s)) {
answer.add(i);
}
}
return answer;
}
}
优化后，使用滑动窗口+HashMap的样式
class Solution {
private HashMap<String, Integer> wordCount = new HashMap<String, Integer>();
private int n;
private int wordLength;
private int substringSize;
private int k;
private void slidingWindow(int left, String s, List<Integer> answer) {
HashMap<String, Integer> wordsFound = new HashMap<>();
int wordsUsed = 0;
boolean excessWord = false;
// Do the same iteration pattern as the previous approach - iterate
// word_length at a time, and at each iteration we focus on one word
for (int right = left; right <= n - wordLength; right += wordLength) {
String sub = s.substring(right, right + wordLength);
if (!wordCount.containsKey(sub)) {
// Mismatched word - reset the window
wordsFound.clear();
wordsUsed = 0;
excessWord = false;
left = right + wordLength;
} else {
// If we reached max window size or have an excess word
while (right - left == substringSize || excessWord) {
String leftmostWord = s.substring(left, left + wordLength);
left += wordLength;
wordsFound.put(leftmostWord, wordsFound.get(leftmostWord) - 1);
if (wordsFound.get(leftmostWord) >= wordCount.get(leftmostWord)) {
// This word was an excess word
excessWord = false;
} else {
// Otherwise we actually needed it
wordsUsed--;
}
}
// Keep track of how many times this word occurs in the window
wordsFound.put(sub, wordsFound.getOrDefault(sub, 0) + 1);
if (wordsFound.get(sub) <= wordCount.get(sub)) {
wordsUsed++;
} else {
// Found too many instances already
excessWord = true;
}
if (wordsUsed == k && !excessWord) {
// Found a valid substring
answer.add(left);
}
}
}
}
public List<Integer> findSubstring(String s, String[] words) {
n = s.length();
k = words.length;
wordLength = words[0].length();
substringSize = wordLength * k;
for (String word : words) {
wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
}
List<Integer> answer = new ArrayList<>();
for (int i = 0; i < wordLength; i++) {
slidingWindow(i, s, answer);
}
return answer;
}
}